/**
 * [142] 环形链表 II
 * https://leetcode.cn/problems/linked-list-cycle-ii/description/
 *
 * 如果链表无环，则返回null。
 * 如果链表中存在环，则返回环的入口节点。
 */

public class Solution142 {

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        boolean is = false;

        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if(fast == slow){
                is = true;
                break;
            }
        }
        if(is){
            fast=head;
            while(fast!=slow){
                fast=fast.next;
                slow=slow.next;
            }
            
        }
        return is?fast:null;
    }
}